The present invention relates generally to asynchronous circuits and logic and more particularly to an asynchronous circuit employing a plurality of logic gates interconnected such as to insure a high degree of reliability in transfer and storage of digital information, and further relates to a family of logic systems employing said circuits; which systems may be readily interfaced with one or more external synchronous or asynchronous systems either in the parallel or serial mode of operation.
Asynchronous circuits and systems have been the subject of considerable investigation in recent years due to the theoretical increase in speed of operation which can be achieved with such circuits. The results of such investigations have been the subject of several publications and at least one patent. The results of previous work in this field by the present inventor formed the subject matter of his Master's Thesis at the University of Pennsylvania, August, 1964, entitled "Practical Asynchronous Circuits". One of the circuits disclosed in said Thesis is reproduced in FIG. 2 of the drawings accompanying this application and is described in detail relative to said Figure. As will become apparent from the description of FIG. 2, that circuit suffers from many of the defects and problems encountered in the work of others in this field, some of this work being described immediately below.
U.S. Pat. No. 3,378,776 to Goldberg et al describes a prior art asynchronous system wherein logic circuits are employed to transmit and store binary information. In this system, (hereinafter referred to as the "anti-parallel" system) there is provided a plurality of cascaded storage stages including storage elements and control circuits for controlling transfer of information from one stage to another in response to a gate pulse applied to the last stage of the cascade and transmitted on a stage-by-stage basis toward the first stage of the cascaded circuit. Information is stored as a binary 1 or binary 0 and upon the application of the gate pulse to the last stage, the information in that stage is transferred to a read-out circuit. After a short delay the gate pulse is regenerated and applied to the preceding stage so that information stored therein is transferred to the last stage and so on up the chain. Thus the control pulses proceed in a direction opposite to the direction of propagation of the information.
As in other prior art asynchronous devices difficulties arise due to pulse "races" both intrastage and interstage. This difficulty stems from time delays through various gates in a stage and the accumulated time delays in one stage relative to accumulated time delays in an adjacent stage. Each stage has a minimum recovery time between the time of application of a gate pulse and the time at which a new unit of information may be received; i.e., the circuit can respond to a second pulse gate. If a gate pulse is applied to a specific stage before the end of the minimum recovery time, the stage would not normally be able to respond, information would be lost and the gate pulse would not be transmitted to the preceding stage.
In response to occurrence of the above situation, a space symbol is automatically generated and introduced into the chain of information. The space symbol is a specified combination of voltage levels on the information leads and is different from the voltage levels for either the binary 1 or the binary 0. For instance, assume that the information circuit comprises two leads emanating from an information storage circuit. If a binary 1 is stored by the circuit, one lead has a binary 1 and the other lead has a binary 0 developed thereon. If a binary 0 is to be transmitted the above arrangement is reversed. If a space symbol is to be transmitted both leads have a binary 0 applied thereto.
By the use of the above arrangement it is possible to prevent loss of information but the speed of operation of the circuit is greatly reduced due to dispersion of the information along the stages. The reduction of speed of operation becomes increasingly severe as the circuits age since each circuit, in fact each gate in each circuit, is affected differently so far as time response is concerned, by the aging process. Thus as circuits age in an anti-parallel system the speed of operation declines steadily.
The anti-parallel system has a further disadvantage which is associated with the manner of control of transmission of information. Information is transmitted down the chain only in response to application of a gate pulse to the last stage from an external source. Thus the system is actually "clocked" be the read-out on external circuits and cannot operate at the inherent speed of asynchronous circuitry which ideally is faster than synchronous circuits. In consequence, much of the time advantage ascribed to such circuits is lost not only due to external clocking but also due to the fact that the asynchronous circuit cannot function (transfer information) until the read-out circuit is ready to receive information. It is thus not only possible but probable that an anti-parallel chain may remain devoid of information even though the circuit which is to feed information thereto is ready to supply information, and the chain is ready to receive information, only because the read-out circuit is not ready to receive new information.
Another asynchronous circuit of the prior art which is of interest is the circuit of Muller described in his article "Asynchronous Logics and Application to Information Processing", Switching Theory in Space Technology, 1963 Standford University Press.
Muller provides a true asynchronous circuit in that transmission of information down a cascaded chain of stages is primarily under the control of the stages themselves. Muller also employs circuits having three stages; a binary 1 state, a binary 0 state and a neutral state N. However Muller also has trouble with pulse "races" within each stage and between stages and in order to overcome such problems, Muller, as did the present inventor in his prior art circuit illustrated in FIG. 2, employs both feedback and feedforward control signals and prescribes certain rules for transmission of information as determined by the condition of any three adjacent stages. Specifically, Muller permits transfer of information only when the following combinations of states exist in three adjacent stages:
1. INN
2. NII
where I is an information state (binary 1 or 0) and N is a neutral state.
When the first combination of states above is developed in the Muller device, a shift occurs to the INN combination, whereas the NII combination shifts to the NNI combination. No other combination of states permits a further transmission of information. Thus if four stages are considered having the following arrangement of information I.sub.1 NNI.sub.2 the information I.sub.1 proceeds to the second stage I.sub.1 I.sub.1 NI.sub.2, but cannot progress further toward the stage storing I.sub.2 until the information I.sub.2 is removed from the last stage being considered above. If the last stage above is the last stage of the chain, then upon removal of the information I.sub.2 from the last stage, the information I.sub.1 is transmitted to the last stage through the next to the last stage. If the last stage above is in the middle of a chain, then the succeeding two stages must assume their neutral states before information I.sub.2 can be transmitted.
Thus the aforesaid circuits, due to constraints placed on the system to avoid dangerous pulse races must sacrifice speed for accuracy. Further the gate logic is complex and therefore expensive.
With both the anti-parallel and the Muller circuits, difficulties and real complexities are encountered at the interfaces with other types of logic both relative to the input and output functions. Further parallel read-in and read-out and fan-in and fan-out can be realized only at such great cost and loss of speed of operation that the advantages expected to be achieved with asynchronous circuits are all but lost.
As will become apparent subsequently, the difficulties encountered with the circuits described above are also encountered with the circuit of FIG. 2 of the accompanying drawings.
It is an object of the present invention to provide an asynchronous circuit that is simple, inexpensive and which is substantially free of intrastage and interstage pulse races.
It is yet another object of the present invention to provide an asynchronous circuit and system employing cascaded asynchronous circuits in which intrastage and interstage races are inherently eliminated due to the fact that pulses which might otherwise produce races are always transmitted through different numbers of identical gates.
It is another object of the present invention to provide an asynchronous circuit which transfers information from stage-to-stage at a rate determined wholly by the internal timing of the circuits.
It is still another object of the present invention to provide a tristable asynchronous circuit and logic having binary information states and a neutral state in which the intercircuit logic is wholly defined by the interaction between any two adjacent stages.
Yet another object of the present invention is to provide a tristable asynchronous circuit and system wherein when any two adjacent stages have stored therein I and N in the first and second stages, respectively, information is immediately transferred such that the stages assume the pattern N and I respectively, regardless of the condition of any one or more other stages of the cascade of circuits.
It is another object of the present invention to provide cascade asynchronous stages in which information received at the first stage of the circuit is transmitted, at a rate determined wholly by the internal logic of the apparatus, to the first succeeding stage of the cascaded stages which is not storing information.
It is still another object of the present invention to provide an asynchronous circuit and system of cascaded stages which, when operated with synchronous systems having a clock pulse rate slower than the transmission rate of the asynchronous system, appears as an elastic memory since the cascaded asynchronous device appears to have a number of stages equal only to the number of units of information stored therein.
Still another object of the present invention is to provide an asynchronous circuit which may be readily fed information in serial or parallel and have information readily extracted in serial or parallel.
It is yet another object of the present invention to provide an asynchronous circuit and system which may be interfaced with external circuits by means of quite simple interface circuits.
It is another object of the present invention to provide a tristable asynchronous circuit which upon receipt of the information stored therein by a succeeding stage always resets itself to a neutral state and signals the preceding stage that it is available to receive additional information.
It is still another object of the present invention to provide an asynchronous circuit having a storage section, a gate (out) section and a control section, the latter of which is responsive to receipt of information by the succeeding stage to terminate transfer of information to the succeeding stage and one gate interval later to reset its stage to neutral so that it may now receive information from the preceding stage.
It is yet another object of the present invention to provide cascaded asynchronous stages in which the transmission rate of information is greater than the rate at which each stage can be completely cycled.
Still another object of the present invention is to provide cascaded asynchronous circuits which may transmit information in either the forward or reverse directions.
Another object of the present invention is to provide a novel adder circuit employing cascaded asynchronous circuits of the present invention.
Yet another object of the present invention is to provide a plurality of parallel cascaded asynchronous logic circuits which although asynchronous in operation are constrained to transmit information through certain stages of one chain in synchronism with the corresponding stages of the parallel chain or chains.
According to one preferred realization of the present invention there is provided an eight NAND gate circuit including a storage section, an output gate section and a control section. The storage section comprises three gates cross-coupled to provide a flip-flop like arrangement having to develope on two information lead signals, three stable states, 1-0 (I), 0-1 (I) and 1-1 (N). The gate section comprises two gates, each for gating out signals on a different one of the information leads. The output gates are controlled by the control section and a third gate of the storage section whose output lead is not one of the information leads.
The control section employs three gates, two of which are cross-coupled and in conjunction with the third gate provide a circuit which through part of an information transfer cycle is bistable and through another part of the cycle is monostable.
The third gate of the storage section senses the voltages on the output leads of the other two storage section gates and when the voltages on the information leads indicate the neutral state, such third gate signals the preceding stage that its stage is ready to receive information. When information is received by the stage, this third gate blocks further information transfer from the preceding stage and applies a gate to the output gates of its own stage. The output gates are not opened however until the succeeding stage transmits a signal indicating that it is in the neutral state and that it can receive information. At this point the control section of the stage opens the output gates of the stage and permits information to be transmitted. The succeeding stage, upon receiving such information, changes its signal to the stage under consideration whose control section then closes the output gates and resets the storage gates to the neutral state. The control section thereafter again opens the output gates when the signal from the succeeding stage signifies that such stage is in its neutral state, and therefore ready to receive new information.
An important feature of the operation described above is that each stage is reset to the neutral state between successive information states. The neutral state is a stable state in the device of the present invention and thus a stage is set to an information state only in response to positive recognition of the transfer of information from a preceding stage. The above procedure is in contradistinction to the prior art devices in which a preset time interval is provided between transmission of information signals and in which if the information in a prior stage has not changed during this interval the same information may be transmitted twice.
As a result of the operation of the present invention, each stage of the system is either isolated from or placed in communication with a preceding or succeeding stage in dependence only upon the internal state of each stage. As soon as an adjacent succeeding stage is ready to receive information, the information is made available regardless of the condition of the stage preceding the stage in question. Thus the cascaded circuit of the present invention may be treated in pairs of stages rather than in triplets of stages as in Muller, as in the present inventor's prior work.
Specifically, the transmission of information in the present invention follows as to any two stages, the pattern IN.fwdarw.NI throughout the length of the chain. In consequence information is transferred along the line of progression to the last stage which does not have information, completely independently of the operation of external circuits.
A further feature of the invention resides in the fact that parallel feed-in or feed-out of information may be readily achieved. As to parallel input, since the storage gates are the input elements of each stage, information may be applied directly to these gates without any problems. Also, since information stored in each stage is always available to external circuits, parallel read-out is easily accomplished.
Fan-in and fan-out of information are also simple tasks for the circuits. By employing interrelated interface devices, which, as will become apparent from the detailed description of the circuits, are quite simple, the cascaded stages may accept or gate out information in the alternative from or to two or more input or output circuits on a one-for-one or block-by-block basis. Thus the circuits find immediate use in multiplexing, de-multiplexing and adder functions.
Due to the interconnection of the three parts of each stage, information is transmitted through a stage in less than the overall cycle time of the stage. It was stated above that the stage gates have their input leads and output leads cross-coupled so that information applied to the storage gates is also applied at the same time to their output leads. Thus the only delay in transferring information is first through the third storage gate which opens the output gates (assuming the succeeding stage is ready to receive information) and then through the output gates to the next stage. Thus full transmission of a unit of information is accomplished in two gate delay intervals, or a few nanoseconds, even though the complete cycling of a stage takes somewhat longer due to delay in the feedback signal from the succeeding stage and resetting of the stage to neutral before the next unit of information can be accepted.
The pulse or signal race problem is greatly reduced if not eliminated in the present circuit and systems, since any group of events proceeding from the receipt of a sepcified signal are accomplished, although concurrently, through different numbers of gates. For instance, when a signal is received from a succeeding stage indicating that such stage has received information, the stage under consideration produces a pulse closing its output gates and resetting the storage gates to neutral. The closing of the output gates must occur before the resetting of the storage gates. In accordance with the control circuit, the gate-closing signal closes the gates after a one gate delay but the storage gates are reset only after a two gate delay, one gate in the control section and the storage gates themselves. The above procedure is followed throughout the circuits of the system and embodiments are disclosed which insure proper operation even in those instances where excessive differences in gate delays might be encountered due to excessive aging.
An additional feature of the invention resides in the control section of the circuits. The circuits of the control section, as a separate unit, has been found to be highly useful as an interface device for both read-in and read-out of information to or from the circuits as is described in detail subsequently. As previously indicated, the control section circuit operates as a flip-flop over a part of its cycle and as a monostable device over another part of its cycle of operation. As such, it may be set into one or another state when certain conditions exist in the circuit (when information is being inserted into the system but the circuits which are to accept readout are not ready) but operates as a self recycling device when readout has been accepted. In the interface situation this type of circuit is ideal because it can stabilize a system in one of two quiescent states but can cycle the system when a transient operation is required such as information transfer and subsequent termination of transfer and resetting of the storage gates to neutral.
As indicated above, the control section of the circuit of the present invention may be utilized as a separate entity apart from the circuit. Conversely the control section may be replaced for particular application to achieve special effects. In one such example, the real time adder of FIG. 21 employs a special control section to achieve a special data processing effect. In the case of the real time adder the special circuit is also autosynchronous.
The apparatus of the invention is capable, with minor modification, of transmitting information in one or the other direction in dependence upon external control signals and may operate as an asynchronous reversible shift register without losing any of the benefits of the basic circuit.
The embodiments of the invention initially set forth above have wide applicability to many systems only a few of which are described herein. Specifically the circuit may be employed as an elastic shift register, in a multiplexer or demultiplexer, for fan-in, fan-out and recirculating information loops and in parallel synchronized circuits as in an adder. In summary, the present invention provides an asynchronous circuit or circuits and systems employing the same, which are very fast, highly reliable and unusually versatile, may be readily interfaced with conventional digital circuits with little additional and uncomplicated sandardized circuitry, and which is devoid of most of the problems which have plagued prior art asynchronous devices.
An additional feature of the present invention is the use of specific NAND gates wired in a predetermined manner to produce a quasi-NOR function. More particularly, the output leads of two NAND gates are directly connected together so that if one of the gates has signals (1's) applied to all of its input leads the output signal of the combination of gates is determined (0) regardless of the condition of the input leads of the other NAND gate. The utilization of the above specific combination of gates permits elimination of buffering gates and the delay which attends addition of any gates to the circuit. Since high speed operation is an important feature of the invention, elimination of over one gate delay per stage is important.